import numpy as np
import  time

start =time.time()
A = [[30,35], [35,15], [15,5], [5,10], [10,20], [20,25]]
n = np.shape(A)[0] #获得连乘矩阵的个数n
m = np.zeros((n, n, 2), dtype=int) #存储[i,j]从Ai到Aj的[最小计算次数, 最优断开点s]

def matrixChainDirect(A):
    for k in range(1, n):  #从2个矩阵连乘开始，计算到n个矩阵连乘。
        for i in range(0,n-k): #从第i个矩阵开始连乘k个矩阵
            minCount = 0
            minS = i
            for s in range(i,i+k): # A_i * A_i+1 *... *A_i+k-1 矩阵连乘从s处断开
                count = m[i][s][0] + m[s+1][i+k][0] + A[i][0]*A[s][1]*A[i+k][1]
                if (s==i) or (count<minCount):
                    minCount = count
                    minS = s
            m[i][i+k] = [minCount, minS]
    return m


# 输出Ai到Aj的最优计算方式，类似(A0(A1A2))((A3A4)A5))
def traceS(mm, i, j):
    if i == j:
        return 'A' + str(i)  # 只剩余一个矩阵，则返回‘Ai’
    if (i + 1) == j:
        return 'A' + str(i) + 'A' + str(j) + ''  # 剩余2个矩阵，则返回‘AiAj’

    # 否则，分成左右两个部分
    leftStr = '(' + traceS(mm, i, mm[i, j, 1]) + ')'
    RightStr = '(' + traceS(mm, mm[i, j, 1] + 1, j) + ')'
    return leftStr + RightStr

matrixChainDirect(A)
print('最优计算次数：')
print(m[:,:,0])
print('最优断开处：')
print(m[:,:,1])
print('最优计算方式：')
print(traceS(m, 0, n-1))
end = time.time()

print('耗费时间： '+str(end-start)+'s')

# 从两两矩阵开始相乘，其实两两矩阵相乘分界点必然是两者之间
# 开始三三相乘算起，判断其分界点
# 。。。。。。。四四    五五。。。。。 XX 相乘
# 形成 2-5  3-5 4-5 的最有断开矩阵
# 其实实际上是对计算次数进行了分析
# 之后按照分析的结果进行计算
# 分析时间大概为 0.001秒  其实大大减少了计算量